typedef struct _Range {
  int start, end;
} Range;
Range new_Range(int s, int e) {
  Range r;
  r.start = s;
  r.end = e;
  return r;
}
void swap(int *x, int *y) {
  int t = *x;
  *x = *y;
  *y = t;
}
void quick_sort(int arr[], const int len) {
  if (len <= 0)
    return; // 避免len等於負值時引發段錯誤（Segment Fault）
  // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素
  Range r[len];
  int p = 0;
  r[p++] = new_Range(0, len - 1);
  while (p) {
    Range range = r[--p];
    if (range.start >= range.end)
      continue;
    int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點
    int left = range.start, right = range.end;
    do {
      while (arr[left] < mid)
        ++left; // 檢測基準點左側是否符合要求
      while (arr[right] > mid)
        --right; //檢測基準點右側是否符合要求

      if (left <= right) {
        swap(&arr[left], &arr[right]);
        left++;
        right--; // 移動指針以繼續
      }
    } while (left <= right);

    if (range.start < right)
      r[p++] = new_Range(range.start, right);
    if (range.end > left)
      r[p++] = new_Range(left, range.end);
  }
}